a) Field of the Invention
The present invention relates to a method and associated computer software for improved visualization and interaction with three dimensional graphics, whereby the system renders only what the user sees and does not waste time rendering hidden components.
b) Description of Related Art
Recent modeling simplification efforts, using Computer Aided Design (CAD) systems, focus on reducing the number of polygons in a visual model. Surfaces in CAD model are tessellated to generate polygons. The collection of polygons is then used as a visual model. The current method relying on the polygon based “Level of Details” (LOD) approach is unwieldy. It requires loading all the information about the entire mechanical model. Such a data set far exceeds the capability of present-day graphics hardware to interactively render the model, no matter the polygon count. Today, modeling applications demand an instantaneous, interactive display of models.
Heckbert in “Ten Unsolved Problems in Rendering, Workshop on Rendering Algorithms and Systems” provided a list of ten unsolved problems in simplifying models for rendering. Among them is the problem of how to more fully automate the levels of details and hierarchical bounding boxes. Heckbert noted that setting up a level of details database is burdensome and causes uneven transitions when switching levels. For simulation work, this is quite unacceptable.
Researchers have investigated and pursued numerous simplification approaches. Among them are the octree, wavelet and the favored multi-resolution technique. Srihari in “Multi-resolution 3-d Image Processing and Graphics” showed how octree models can be used for displaying voxel-based images at different levels of detail. In an octree, each level of the tree increases the resolution by a factor of eight. This allows one to view an object as a gradual process proceeding from a father node to its sons. Gortler, et al in “Hierarchial and Variational Geometric Modeling with Wavelengths” used the hierarchical nature of wavelet basis functions to obtain multi-resolution control point and ]east squares control. A wavelet basis represents a solution hierarchically. In wavelet based schemes, the user chooses the resolution level 1, and then only the quantities of basis function on level 1 are altered. However, multi-resolution models are the models of choice for simplifying renderings and simulations. A few researchers such as Harten (“Multiresolution Representation and Numerical Algorithms”) and Gauch (“Multiresolution Image Shape Description”) have developed multiresolution techniques.
In 1994, Heckert et al. presented “Multiresolution Modeling For Fast Rendering” which surveyed multi-resolution techniques for accelerated rendering and found that a polyhedral simplification method was the most appropriate for accelerated rendering and simulation. Subsequently, commercial packages that used the multi-resolution technique became available. Among them are: the 3D Accelerator (see Rossignac et al., “Multi-resolution 3D approximations for rendering complex scenes”), a polyhedral simplification method, and Deneb Robotics optional package called HIFI, which is a polygonal simplification method.
However, the multi-resolution modeling technique has limitations. Multi-resolution models are scene dependent. They require the preparation of a level of details database for each scene. This is a lengthy process that requires input from the user for each scene and each model. All objects (external and internal) must be prepared, stored in the database, and rendered whether or not the objects are visible during the simulation.
Decomposing a CAD model into polygons before rendering it for visualization typically produces thousands of polygons. The software algorithms that underlie the modeled object, generate an even smaller set of polygons that are visually similar to the original object. By creating multiple levels of detail (fore, mid and background) at varying resolutions, the work of a graphics engine is reduced. However, important visible features are lost in such simplification processes. Moreover, the polygonal simplification methods still cannot deliver the requisite display speed for large mechanical models.
A mechanical environment consists of whole mechanical parts and assemblies. A person recognizes a piece of equipment not by taking it apart and investigating its internals, but by simply looking at its external surfaces, its “container.” No one needs to take apart an automobile to recognize what it is, even though the interior parts are hidden from the viewer. The polygon based LOD technique loads all the information, both interior and external, and does not take advantage of the physical reality of a mechanical environment.